语言与机器
计算模型大致可分为两类：一类是 λ 演算，另一类则是除此之外的所有模型。或许 Post 的产生式系统和 Herbrand–Gödel 方程也应归入前者，但毫无疑问，像图灵机、随机存取机（RAM）这些广为人知且被广泛接受的模型，与 λ 演算有着本质的不同。
Guy Blelloch 曾将这种区别概括为“语言”与“机器”的对立。基于机器的模型都建立在一个共同理念之上：一个有限的控制器，外加无限的存储空间。程序员必须亲自管理内存，才能实现比“比特”更复杂的结构；而且，除非借助解释器，否则程序在运行过程中无法被修改——这些模型本质上是非冯·诺依曼式的，因为它们缺少“程序可存储”的核心思想。
相比之下，λ 演算作为唯一的语言型计算模型，不区分程序与数据，为构建现实世界的编程语言提供了直接而无需编码的基础。这看起来是一个压倒性的优势：教科书里那些机器模型虽然出现在前几章，但在实际应用中几乎毫无用处；而 λ 演算却能直接用于编程，也能支撑逻辑系统的机械化推理。
然而讽刺的是，在算法与复杂性理论等主流领域，占据主导地位的恰恰是这些“过时”的机器模型，而 λ 演算则被视为一种冷门奇技，只有少数计算机科学家才会深入研究。这是为什么？
面对这个问题，我的许多理论方向的同事通常会不屑一顾：“所有计算模型在多项式时间内都是等价的，谁还在乎细节？”
的确，如果你的研究只关心自然数（或其他有限对象）上的计算，并且对复杂度的分析允许忽略多项式因子，那么模型的选择似乎无关紧要。你只需一次性说明如何在某个模型上表示你的对象，然后就可以高枕无忧了——细节真的不重要。
但事实显然并非如此。同一个同事绝不会考虑用 λ 演算或任何非机器模型作为自己工作的基础！如果所有模型真的等价，那为何不能换用 λ 演算呢？理论上或许可行，但现实中没人买账。看来，有些模型“更等价”一些！
为什么会这样？一个原因是：很多实际工作根本不能容忍“差一个多项式因子”。对于这些场景，模型的选择就至关重要。另一方面，没有人真的用“官方”模型写算法——没人会用图灵机代码描述算法，甚至也很少有人写 RAM 代码（Knuth 除外）。大家写的其实是某种“混合 Algol”、“伪 C”之类的命令式伪代码。也就是说，人们实际上是在用编程语言，而不是机器！
既然如此，为何还要执着于机器模型？这些伪代码到底意味着什么？
答案是：这些语言通过（非正式但足够清晰的）“编译规则”被映射到机器模型上。例如，“这段伪代码对应某段 RAM 指令”。虽然描述并不严格，但足以让人理解其含义。关键在于，我们推理的对象不是自己写的伪代码，而是它被“编译”后生成的机器代码——因为后者才是“真正”的程序，前者只是方便表达的工具。
为了做到这一点，我们必须在头脑中“内置”一个编译器：看到每一行伪代码，都要能想象出它在 RAM 上如何执行。只要伪代码足够简单，这种“脑内编译”尚可应付。但随着算法日益复杂，这种限制越来越成为瓶颈——它束缚了我们表达和分析算法的能力。
那么，为何还要坚持这套别扭的做法？一部分原因当然是传统：“我导师当年就这么干的，我也这么干。”或者更现实一点：“审稿人熟悉这套语言，想发表就得按他们的规矩来。”
但更深层的原因在于：机器模型为计算成本提供了明确的度量标准。我们把“一步计算”定义为一次机器操作，并据此比较不同算法解决问题所需的步骤数（通常允许常数倍差异）。只要我们能“手动编译”伪代码到机器指令，就能为高级语言写出的程序赋予运行成本，从而理性地比较算法效率。
这套方法过去非常成功，但如今正逐渐失效（并行计算就是一大挑战，此外还有很多问题，此处暂不展开）。
其实还有另一种选择：直接为高级语言本身定义“成本语义”，并在该语义基础上进行分析，完全绕开底层机器和编译过程。换句话说，采用语言模型而非机器模型，反而能让事情变得更简单、更灵活——我们能用更丰富的语言表达算法，也能更自然地分析它们。
要做到这一点，就需要为实际使用的语言建立一套成本语义。而这正是 λ 演算大显身手的地方。作为语言型计算模型的典范，λ 演算的核心概念是“规约”（reduction），记作 ( M \to M' )，表示程序 ( M ) 执行一步后变为 ( M' )。计算直接作用于我们写的程序本身，每一步规约都有明确定义，因此可以直接计数以衡量时间复杂度。
几十年来的实践表明，这种方法完全可以扩展到现代编程语言。
既然如此，还有什么理由不喜欢 λ 演算呢？我个人实在想不出。我一直困惑于算法领域对 λ 演算那种莫名的怀疑态度——明明几乎所有机器模型都被视为合理基础，但整个领域的实践却又暴露出机器模型在真实研究中的局限性！
除了学术惯性之外，我唯一能想到的解释是：人们仍心存疑虑，认为 λ 演算中的“计算步”不适合作为算法分析的成本单位。（曾有研究者对我说：“你可以在一次 β-规约里藏下一头大象！”但他却说不出我错在哪里。）
其实，这个问题早有解答。早在 1990 年代初，Blelloch 和 Greiner 就已证明：存在一个从 λ 演算到 RAM 的编译方案，使得每一次 λ 规约都能在 RAM 上以常数时间完成（这里的“常数”指与输入规模无关，仅依赖于静态程序大小）。详情可参见 Guy Blelloch 的个人网页。
在后续文章中，我会进一步展开这一思路，并展示（基于 Blelloch 的工作）：λ 演算不仅适用于串行算法，同样能优雅地刻画并行算法！而且，我们还能轻松将其扩展到支持高阶函数、异常处理等现代语言特性的系统中，而不会损害其在算法表达与分析上的实用性。